package main

import (
	"fmt"
)

/*
最小的 k 个数
输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。
*/

//冒泡排序
/*
func getLeastNumbers(arr []int, k int) []int {
	for i:=0;i<len(arr)-1;i++ {
		flag := true
		for j:=0;j<len(arr)-1;j++{
			if arr[j]>arr[j+1]{
				ss:=arr[j]
				arr[j]=arr[j+1]
				arr[j+1]=ss
				flag = false
			}
		}
		if flag == true{
			return arr[:k]
		}
	}
	return arr[:k]
}
*/

//直接排 sort.Ints
/*
func getLeastNumbers(arr []int, k int) []int {
	sort.Ints(arr)
	return arr[:k]
}
*/

func getLeastNumbers(num []int, k int) []int {
	quick(num, 0, len(num)-1)
	return num[:k]
}

//快速排序
func quick(num []int, start, end int) {
	if start < end {
		i, j, key := start, end, num[(start+end)/2]
		for i <= j && num[i] < key {
			i++
		}
		for i <= j && key < num[j] {
			j--
		}
		if i <= j {
			num[i], num[j] = num[j], num[i]
			i++
			j--
		}
		if i < end {
			quick(num, i, end)
		}
		if start < j {
			quick(num, start, j)
		}
	}
}

func main() {
	num := []int{4, 5, 6, 1, 9, 6}
	k := 2
	fmt.Println(getLeastNumbers(num, k))
}
